package text;

import java.util.Arrays;
import java.util.Random;

public class QuickSort1 {
    public static void main(String[] args) {
        Random a = new Random();
        int[] x = new int[10];
        for (int i = 0; i < x.length; i++) {
            x[i] = a.nextInt(1000);
        }
        System.out.println("数组的初始样子" + Arrays.toString(x));
        System.out.println("开始排序");
        /*执行快速排序*/
        quickSort(x,0,x.length-1);
        System.out.println(Arrays.toString(x));
    }
    /*
    * 这是一个自定义的方法，方法声明可以参考main（）方法
    * 注意：快速排序本质上没有拆分出新数组，也不需要合并，所以该方法不需要返回值
    * @param x 原数组
    * @param start 需要被拆分的区间的起始元素下标
    * @param end   需要被拆分的区间的结束元素下标*/
    public static void quickSort(int[] array,int start,int end){
        /*使用新的变量表示枢纽元位置的元素值*/
        int pivot = array[end];
        /*创建新的变量，用于表示“左侧区间”的最大下标（最右侧元素的下标*/
        int x = start-1;
        /*遍历数组片段*/
        for (int i = start;i<end;i++){
            /*判断当前元素是否小于或等于枢纽元*/
            if (array[i]<= pivot){
                /*判断当前元素的左侧是否已存在大于枢纽元的元素*/
                if (i-x>1){
                    /*将下标i与下标x+1的数据换位*/
                    int temp = array[i];
                    array[i] = array[x+1];
                    array[x+1] = temp;
                    /*x自增*/
                    x++;
                }else {
                    /*更新x位置*/
                    x=i;
                }
            }
        }
        /*将枢纽元放在左右两个区间的中间
        * 交换枢纽元与第一个大于枢纽元的位置的位置*/
        if (pivot <array[x+1]){
                array[end] = array[x+1];
                array[x+1] = pivot;
        }
        /*如果左侧区间仍有多个元素，则递归*/
        /*因为x是左侧区间的最大下标（最右侧元素下标）
        * 若比需要处理的数组片段的最左侧元素下标大，则表示左侧区间存在超过1个元素*/
        if (x>start){
            quickSort(array,start,x);
        }
        /*如果右侧区域仍有多个元素，则递归*/
        /*x是左侧区域的最大下标，其右侧还有一个枢纽元，如果存在右侧区域，则起始下标为x+2*/

        if (end -x -1>1){
            quickSort(array,x+2,end);
        }

    }
}
